#include <iostream>
#include <vector>
#include <string>
using namespace std;

void SubGenerateParenthesis(int left, int right, string str, vector<string> &res);
vector<string> generateParenthesis(int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<string> res;
	SubGenerateParenthesis(n, 0, "", res);
	return res;
}

void SubGenerateParenthesis(int left, int right, string str, vector<string> &res){
	// if nothing left
	if(left == 0 && right == 0){
		res.push_back(str);
		return;
	}
	if(left > 0){
		// try to use a left
		SubGenerateParenthesis(left-1, right+1, str+"(", res);
	}
	if(right > 0){
		// try to use a right
		SubGenerateParenthesis(left, right-1, str+")", res);
	}
}

int main(){


	return 0;
}